from typing import List

"""
尽可能多的片段
同一个字母只会出现在其中的一个片段。
返回一个表示每个字符串片段的长度的列表。

思路，先找第一字母和后面可能会有的重复字母，找的时候记录，现有，新添加的字母，确保找到最后一个相同字母的时候，后面的字母中也没有新加入的字母
如果后面没有这个字母，那么就单独划分一个区域
"""


class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        res = []
        p1 = 0
        while p1 < len(S):
            index = S.rfind(S[p1], p1 + 1)
            if index == -1:
                res.append(1)
                print("............", p1)
                p1 += 1
            else:
                p2 = p1
                mem = {S[p1]: True}
                print("-", p2, S[p2], mem, index)
                while p2 < index:
                    p2 += 1
                    print(S, p2)
                    if S[p2] not in mem:
                        p2_index = S.rfind(S[p2], index)
                        # if p2_index != -1:
                        index = max(index, p2_index)
                        mem[S[p2]] = True
                        print(mem, index)

                res.append(p2 - p1 + 1)
                p1 = p2 + 1

        return res
        # print(res)


if __name__ == "__main__":
    print(Solution().partitionLabels("ababcbacadefegdehijhklij"))
